/*
 * heap.c
 *
 *  Created on: 2012-5-20
 *      Author: hujin
 */

#include <stdio.h>
#include <stdlib.h>
#include "heap.h"


heap_t * heap_new(int size) {
	heap_t * ret = malloc(sizeof(heap_t));
	if(!ret) return NULL;
	ret->total_size = size;
	ret->heap_size = 0;
	ret->num_elems = 0;
	ret->data = malloc(sizeof(type_t) * size + 1);
	if(!ret->data) {
		free(ret);
		return NULL;
	}
	return ret;
}

void heap_appenda(heap_t * h, type_t arr[], int len) {
	int i;
	for(i = 1; i <= len ; i ++) {
		h->data[i] = arr[i];
	}
	h->num_elems = len;
}

void heapify(heap_t *h, int i) {
	type_t * data = h->data;
	int l = i << 1, r = l + 1, largest;

	if(l <= h->heap_size && data[l] > data[i]) {
		largest = l;
	}else {
		largest = i;
	}

	if(r <= h->heap_size && data[r] > data[largest]) {
		largest = r;
	}

	if(largest != i) {
		type_t tmp;
		tmp = data[i];
		data[i] = data[largest];
		data[largest] = tmp;
		heapify(h, largest);
	}
}

void heap_build_max(heap_t * h) {
	int i = h->num_elems >> 1;
	for(; i >= 1; i --) {
		heapify(h, i);
	}
	h->heap_size = h->num_elems;
}

/**
 * exchange the head element and the last element in the heap, the decrease the heap size.
 */
int heap_exchange(heap_t * h) {
	if(h->heap_size <= 1) {
		return 0;
	}
	type_t tmp;
	tmp = h->data[1];
	h->data[1] = h->data[h->heap_size];
	h->data[h->heap_size] = tmp;
	h->heap_size --;
	return 1;
}

void heap_destroy(heap_t * h) {
	free(h->data);
	free(h);
}
